﻿//
// Created by Freeman on 2022/3/8.
//

/**
 * 图算法
 */

#ifndef PAT_EXERCISES_GRAPH_HPP
#define PAT_EXERCISES_GRAPH_HPP

// ============================== 参考过题解的问题 ==============================

/**
 * 思路：记录每个顶点的最短路径数，以及能带去的最大救援队数。
 * 在运行Dijkstra算法时同时更新最短路径数。具体见实现。
 */
class PAT_A1003 {
public:
    static void solve();
};

// ============================== 存在问题的题解 ==============================

/**
 * 状态：16/25
 * 问题：未知
 */
class PAT_A1003_Problematic {
    class Node {
        friend class PAT_A1003_Problematic;

    private:
        const int id;
        const int localTeams;                   // 驻扎在本地的救援队数量
        int nPaths = 0;                         // 源点通向此顶点的最短路径数
        int nTeams;                             // 能够带到此顶点的最大救援队数量
        int srcDist = INT32_MAX;                // 距离源点的最短距离
        int destDist = INT32_MAX;               // 距离终点的最短距离
        bool srcFlag = false, destFlag = false; // 源点和终点标记

    public:
        Node(int id, int localTeams) : id(id), localTeams(localTeams) {
            this->nTeams = localTeams;
        }
    };

private:
    std::vector<Node> vertices;
    std::vector<std::vector<int>>* adjMatPtr; // 邻接矩阵
    int nVex, nRoads, srcID, destID;

public:
    PAT_A1003_Problematic() {
        std::cin >> nVex >> nRoads >> srcID >> destID;
        adjMatPtr = new std::vector<std::vector<int>>(nVex, std::vector<int>(nVex, INT32_MAX)); // 初始化为无穷大
        // 读取救援队数量
        for (int id = 0; id < nVex; id++) {
            int localTeams;
            std::cin >> localTeams;
            vertices.emplace_back(id, localTeams);
            Node& node = vertices[id];
            if (id == srcID) {
                node.srcFlag = true;
                node.srcDist = 0;
                node.nPaths = 1;
            }
            if (id == destID) {
                node.destFlag = true;
                node.destDist = 0;
            }
        }
        // 读取道路信息
        std::vector<std::vector<int>>& adjMat = *adjMatPtr;
        for (int i = 1; i <= nRoads; i++) {
            int v, w, length;
            std::cin >> v >> w >> length;
            adjMat[v][w] = adjMat[w][v] = length;
        }
    }

    void solve();

    ~PAT_A1003_Problematic() {
        delete adjMatPtr;
    }

private:
    /**
     * Dijkstra算法，找出每个点距离源点的最短距离和距离终点的最短距离
     */
    int dijkstra();
};

#endif //PAT_EXERCISES_GRAPH_HPP
